#ifndef GRAPH_H
#define GRAPH_H

#include <stdio.h>
#include <stdlib.h>

// Edge list of a graph
typedef struct Edge_t Edge;
typedef struct Vertex_t Vertex; 
struct Edge_t
{
    double weight;
    Vertex* dest_vertex;
    Edge *edge_ptr;
    int on_crit_path;
};

// Vertex list of a graph
struct Vertex_t
{
    int out_degree;
    int in_degree;
    int vertex_id;
    int visited;
    int rank;
    double weight;
    double crit_duration;
    //enum mpi_id;
    Edge *edge_ptr;
    Vertex *next;
    Vertex *prev_crit_vertex;
    int on_crit_path;
};

// Graph is represented by a list of vertex
typedef struct Graph_t
{   
    int num_vertices;
    Vertex *vertex_head;
} Graph;

// Linked path represents a path of a graph
typedef struct Node_t Node;

// A node of a path (represented by a vertex)
struct Node_t
{
    Vertex *vertex;
    Node *next;
};

typedef struct Path_t
{
    Node *head;
} Path;

Graph* create_graph();

// Insert a vertex to graph
int insert_vertex(Graph *graph, Vertex* vertex);

// Get the last vertex of graph
Vertex* get_last_vertex(Graph* graph);

// Insert an edge (vertex1, vertex2) to graph
int insert_edge
(
    Graph *graph, 
    Vertex *vertex1, 
    Vertex *vertex2, 
    double weight
);

// Find the longest path (Critical path) of a graph
int compute_critical_path
(
    Path* topo_path, 
    double *length
);

// Sort the vertices in topological order to path
void topological_sort(Graph *graph, Path *path);

// Helper function for topological sort
void visit(Vertex *vetex, Path *path);

// Print the graph
void print_graph(Graph *graph);

// Write graph to dot format and creates a pdf file
int generate_graph
(
    Graph *graph, 
    const char* dotName, 
    const char* pdfName
);

void free_graph(Graph *graph);

// Insert a vertex to the beginning of a path
void insert(Path *path, Vertex* vertex);

// Append a vertex to the end of a path
void append(Path *path, Vertex* vertex);

// Print path
void print_path(Path *path);

// Free path
void free_path(Path *path);



#endif

